#ifndef __MINSUBARRAYLEN_H__
#define __MINSUBARRAYLEN_H__

#include <vector>
using namespace std;

/*
* leetcode 209 长度最小的子数组
*/

/*
* 给定一个含有 n 个正整数的数组和一个正整数 s, 找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组, 并返回其长度。
* 如果不存在符合条件的子数组，返回 0。
* 
* 例如: {2, 3, 1, 2, 4, 3},  target = 7
* return: 2    {4, 3}
*/

/*
* 使用滑动窗口, 即两个指针指向的子数组范围
* 每次快指针添加元素, 判断范围内总和是否 > 目标
*	若大于, 则判断长度, 慢指针右移, 直到总和 不大于 目标 为止
*		总和计算十分方便, 快指针每次右移, 则总和添加指向的元素
*						 慢指针每次右移, 则总和减去慢指针前一个元素
*/
int MinSubArrayLen(int target, vector<int>& nums) {
	int accumulate = nums[0];
	int result = nums.size() + 1;

	//滑动窗口, 快指针正常向前
	for (int slow = 0, fast = 1; fast < nums.size(); fast++) {
		accumulate += nums[fast];

		//当总和大于目标值时, 慢指针向前, 知道不大于为止
		while (accumulate > target) {
			accumulate -= nums[slow];
			slow++;

			//计算长度
			int size = fast - slow + 1;
			result = result > size ? size : result;
		}
	}

	return result == nums.size() + 1 ? 0 : result;
}

#endif // !__MINSUBARRAYLEN_H__

